package com.sjc.algorithm.sort;

import java.util.Arrays;

/**
 * 快速排序  单边循环法
 * @author by SangJiacun
 * @Date 2020/5/12 10:18
 */
public class SingleCycleSort {

    public static void main(String[] args) {
        int[] arr = new int[]{2,54,23,76,98,123,34,13,74};
        System.out.println(Arrays.toString(arr));

        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序
     * @param arr 待排序的数组
     * @param start 开始位置
     * @param end 结束位置
     */
    private static void quickSort(int[] arr,int start, int end){
        if(start > end){
            return;
        }
        int pivot = partition(arr,start,end);
        quickSort(arr,start,pivot-1);
        quickSort(arr,pivot+1,end);
    }

    /**
     * 单边循环法
     * @param arr 待排序的数组
     * @param start 开始位置
     * @param end 结束位置
     * @return mark所在的索引序号
     */
    private static int partition(int[] arr,int start,int end){
        int pivot = arr[start];
        int mark = start;

        for(int i=start+1; i<=end; i++){
            // 如果遍历的值 小于 基准值
            // mark 往后移动一位
            // 遍历的值 和 mark所在的值交换，
            if(arr[i] < pivot){
                mark++;
                int temp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = temp;
            }
        }

        arr[start] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }
}
